import heapq
import itertools
from dataclasses import dataclass, field
import time
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: float
    count: int  # 用于稳定排序
    item: Any = field(compare=False)  # 不参与比较

class AStar:
    @staticmethod
    def heuristic(node, goal):
        """启发式函数（曼哈顿距离）"""
        return abs(node.boundary.x - goal.boundary.x) + abs(node.boundary.y - goal.boundary.y)

    @staticmethod
    def find_path(start_node, goal_node, quadtree_root):
        start_time = time.perf_counter()
        open_set = []
        closed_set = set()  # 已探索节点集合

        counter = itertools.count()  # 自增计数器
        heapq.heappush(open_set, (0, next(counter), start_node))
        closed_set.add(start_node)

        came_from = {}
        g_score = {start_node: 0}
        f_score = {start_node: AStar.heuristic(start_node, goal_node)}

        path = None
        while open_set:
            _, _, current = heapq.heappop(open_set)
            if current == goal_node:
                path = AStar.reconstruct_path(came_from, current)
                break

            closed_set.add(current)
            for neighbor in current.get_neighbors(quadtree_root):
                if neighbor in closed_set:  # 如果这个邻居节点已探索，跳过。
                    continue
                # 重要！tentative_g是起点到neighbor的代价，目前是对角线长度的累加。
                # 这里以后要改为这个邻居的通行代价。
                tentative_g = g_score[current] + neighbor.boundary.width * 1.414
                if neighbor not in g_score or tentative_g < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g
                    f_score[neighbor] = tentative_g + AStar.heuristic(neighbor, goal_node)
                    heapq.heappush(open_set, (f_score[neighbor], next(counter), neighbor))

        end_time = time.perf_counter()
        print("-----------summery-------------")
        print("总耗时:", round(end_time - start_time, 3), "秒")
        if path is None:
            print("吼吼吼~寻路失败了！找找原因吧！")
            return path
        print("path:", len(path))
        print("visited:", len(closed_set))
        print("open_set:", len(open_set))
        print("__came_from:", len(came_from))
        print("__g_score:", len(g_score))
        print("__f_score:", len(f_score))
        return path

    @staticmethod
    def reconstruct_path(came_from, current):
        """重建路径"""
        path = [current]
        while current in came_from:
            current = came_from[current]
            path.append(current)
        return path[::-1]  # 反转路径